Problem statement: zenit14cki

Zvierací vedci nedávno objavili zvláštny typ koralu, tzv. Pascalov koral. Tento koral rastie do šírky a z jeho tela postupom času vyrastajú a odumierajú hlavičky modrej alebo červenej farby. Niekoľko prvých generácií vyzerá nasledovne:

     M
    M M
   M C M
  M M M M
 M C C C M
M M C C M M

Na začiatku pozostáva koral len z jednej modrej hlavičky. V každej generácii všetky hlavičky zaniknú a objavia sa nové. Ak číslujeme generácie od 1, potom je v \(k\)-tej generácii práve \(k\) hlavičiek. Hlavičky, ktoré vzniknú na kraji, sú vždy modré. \(k-2\) hlavičiek, ktoré vzniknú na miestach medzi dvoma hlavičkami predchádzajúcej generácie sú modré vtedy a len vtedy, ak boli dve pôvodné hlavičky rôznej farby.

Zvieratká by rady tieto koraly rozšírili po mori a chodili sa na ne pozerať. Chceli by preto vedieť, kedy sú koraly najkrajšie. Napíšte im program, ktorý prečíta číslo \(k~(1 \leq k \leq 50,000)\) a vypíše riadok pozostávajúci z písmen M a C popisujúci výzor \(k\)-tej generácie koralu. Medzi každými dvoma písmenka vypíšte jednu medzeru.

Ľahšia verzia

Ak váš program bude fungovať pre vstupy do 1000, môžete získať 15 - 20 bodov.

Príklady

Input:

2

Output:

M M

Input:

7

Output:

M C M C M C M

Input:

13

Output:

M C C C M C C C M C C C M